#!/usr/bin/python
"""Solves the n-queens problem: how to place n queens on a
nxn chess board and counts the calculated solutions.
"""
# $URL: http://yoshiiibox.googlecode.com/svn/trunk/queens.py $ 
# $Id: queens.py 11 2006-12-07 01:04:43Z yoshiii.yoshiii $
# can't remember where i originally found that code...
# author: yoshiii.yoshiii@googlemail.com
__version__ =  "$Revision: 11 $"
#
# some sample output: 
# 0 queens: found        1 solutions in 0.0000 seconds
# 1 queens: found        1 solutions in 0.0000 seconds
# 2 queens: found        0 solutions in 0.0000 seconds
# 3 queens: found        0 solutions in 0.0000 seconds
# 4 queens: found        2 solutions in 0.0001 seconds
# 5 queens: found       10 solutions in 0.0003 seconds
# 6 queens: found        4 solutions in 0.0011 seconds
# 7 queens: found       40 solutions in 0.0046 seconds
# 8 queens: found       92 solutions in 0.0206 seconds
# 9 queens: found      352 solutions in 0.0978 seconds
#10 queens: found      724 solutions in 0.5184 seconds
#11 queens: found     2680 solutions in 2.9843 seconds
#12 queens: found    14200 solutions in 15.3276 seconds
#13 queens: found    73712 solutions in 94.9205 seconds
#14 queens: found   365596 solutions in 672.7201 seconds
#15 queens: found  2279184 solutions in 4209.1158 seconds
#16 queens: found 14772512 solutions in 28904.9411 seconds

import time

sol_counter = 0

def queens( order, rows, solution ):
    global sol_counter
    if order:
        for x in rows:
            y = order - 1
            for i, j in solution:
                if x - y == i - j: break
                if x + y == i + j: break
            else:
                r = rows[:]
                s = solution[:]
                r.remove( x )
                s.append(( x, y ))
                queens( y, r, s )
    else:
#        print solution
        sol_counter += 1

for a in range(10):
    sol_counter = 0
    start = time.time()
    queens(a, range(a), [])
    stop = time.time()
    print "%2i queens: found %8i solutions in %.4f seconds"%(a, sol_counter, stop - start)


